/**
 * 快速排序
 * 每次迭代都将选中的元素排在它整个数组该在的位置
 * 并且比选中的元素小都在它位置的左边，比它大的都在右边
 */
public class QuickSort {
    /**
     * 交换数组下标i和j的值
     * @param nums
     * @param i
     * @param j
     */
    public void swap(int[] nums,int i,int j){
        if (nums==null||i==j)
            return;
        if(i>nums.length||j>nums.length){
            throw new ArrayIndexOutOfBoundsException("数组下标越界");
        }
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 将一轮迭代分区，即实现：把选中的元素放到它应该在的位置，并且左边的元素均比它小，右边的元素均比它大
     * @param nums
     * @param start
     * @param end
     * @return
     */
    public int partition(int[] nums,int start,int end){
        if(nums==null)
            throw new NullPointerException("待排序数组不能为空");
        if(start>end)
            throw new IllegalArgumentException("开始下标不能大于结束下标");
        if(start>=nums.length||end>nums.length)
            throw new ArrayIndexOutOfBoundsException("数组下标越界");
        if(start==end)
            return start;

        //选择最后一个作为参照，也可以使用Math.random随机生成start~end的下标，然后将该下标与end的值交换
        int target = nums[end];
        //分区指示器
        int zoneIndex = start-1;

        /**
         * i遍历数组，当nums[i]小于等于target时，分区指示器右移一位，如果分区指示器不等于i，交换分区指示器和i；当nums[i]大于target时不做任何处理
         * 最后返回分区指示器
         */
        for (int i = start; i <=end ; i++) {
            if(nums[i]<=target){
                zoneIndex++;
                if(zoneIndex<i){
                    swap(nums,zoneIndex,i);
                }
            }
        }
        return zoneIndex;
    }

    public void sort(int[] nums){
        sort(nums,0,nums.length-1);
    }

    /**
     * 递归实现排序
     * @param nums
     * @param start
     * @param end
     */
    private void sort(int[] nums,int start,int end){
        int partition = partition(nums, start,end);
        if(partition>start)
            sort(nums,start,partition-1);
        if(partition<end)
            sort(nums,partition+1,end);
    }

    public static void main(String[] args) {
        int[] nums = {10,8,0,11,32,13,-8,90,55,22};
        QuickSort quickSort = new QuickSort();
        quickSort.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
